using System;
using System.Diagnostics;

namespace ContainsDuplicate
{
    public class Program
    {
        public static void Main1()
        {
            Stopwatch sw = new Stopwatch();
            int testCount = 20;

            // test2
            long t2 = 0;
            System.Console.Write($"test2: ");
            for (int i = 0; i < testCount; i++)
            {
                sw.Reset();
                var arr = makeArr(i % 2 == 0);
                sw.Start();
                ContainsDuplicate2(arr);
                System.Console.Write(sw.ElapsedTicks + " ");
                t2 += sw.ElapsedTicks;
            }
            System.Console.WriteLine();

            // test1
            long t1 = 0;
            System.Console.Write($"test1: ");
            for (int i = 0; i < testCount; i++)
            {
                sw.Reset();
                var arr = makeArr(i % 2 == 0);
                sw.Start();
                ContainsDuplicate(arr);
                System.Console.Write(sw.ElapsedTicks + " ");
                t1 += sw.ElapsedTicks;
            }

            System.Console.WriteLine();
            System.Console.WriteLine($"t1: {t1} \t t2: {t2}");
            System.Console.WriteLine($"t1 { (t1 >= t2 ? ">=" : "<") } t2");

        }

        public static int[] makeArr(bool r)
        {
            int[] largeArr = new int[24500];
            Random random = new Random();
            for (int i = 0; i < largeArr.Length; i++)
            {
                largeArr[i] = r ? random.Next(1, 24500) : (24500 - i);
            }
            return largeArr;
        }


        // 循环比较。 时间复杂度 : O(n^2)
        public static bool ContainsDuplicate(int[] nums)
        {
            if (nums?.Length <= 0) return false;
            for (int i = 0; i < nums.Length; i++)
            {
                for (int j = i + 1; j < nums.Length; j++)
                {
                    if (nums[i] == nums[j])
                        return true;
                }
            }
            return false;
        }

        // 先排序，再比较。 时间复杂度 : O(nlogn)。
        public static bool ContainsDuplicate2(int[] nums)
        {
            Array.Sort(nums);
            for (int i = 0; i < nums.Length - 1; i++)
            {
                if (nums[i] == nums[i + 1])
                    return true;
            }
            return false;
        }
    }
}